package com.lun.swordtowardoffer2.c09;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class TopKFrequent {

	public List<Integer> topKFrequent(int[] nums, int k){
		Map<Integer, Integer> num2Count = new HashMap<>();
		for(int num : nums) {
			num2Count.put(num, num2Count.getOrDefault(num, 0) + 1);
		}
		
		Queue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
				(e1,e2)->{return e1.getValue()-e2.getValue();});
		for(Map.Entry<Integer, Integer> entry : num2Count.entrySet()) {
			if(minHeap.size() < k) {
				minHeap.offer(entry);
			}else {
				if(entry.getValue() > minHeap.peek().getValue()){
					minHeap.poll();
					minHeap.offer(entry);
				}
			}
		}
		
		List<Integer> result = new ArrayList<>();
		for(Map.Entry<Integer, Integer> entry : minHeap) {
			result.add(entry.getKey());
		}
		
		return result.stream().sorted().toList();
	}
	
}
